package arithmetic;
import java.util.HashMap;
import java.util.Map;
/**
 * @author Ajie
 * @date 2024/4/13
 * @function
 *
 *  动态并查集
 */
public class UnionFindDynamic {
    private Map<Integer, Integer> parent = new HashMap<>(); // 存储每个节点的父节点
    private Map<Integer, Integer> rank = new HashMap<>();   // 存储每个【根节点】的秩（树的高度）
    // rank通常表示一个集合树的高度的上界，不一定精确等于树的实际高度，但它是一个衡量树高的重要工具。
    // 它可能代表了树中节点的数量。

    // 查找操作，带路径压缩
    public int find(int p) {
        if (!parent.containsKey(p)) {
            parent.put(p, p);
            rank.put(p, 0);
            return p;
        }
        //第一步：找到根节点
        int root = p;
        while (root != parent.get(root)) {
            root = parent.get(root);
        }
        // 第二步：路径压缩，使路径上的所有节点直接指向根节点
        // 从，下到上，，，从子节点---》根节点，全部压缩。
        while (p != root) {
            int tempparetnt = parent.get(p);
            parent.put(p, root);
            p = tempparetnt;
        }
        //或者 只压缩，p 这 1 个节点，
//        if(p!=root){
//            parent.put(p,root);
//        }
        return root;
    }

    // 联合操作，按 rank 合并， rank表示深度 or 树的数量。，，，rank 小的 附加到  rank 大的 上，更加扁平。
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
//            随便，合并！！！TODO...
//            parent.put(rootP,rootQ);

            // 比较两个根的 rank , rank 大的 附加到  rank 小的上，更加扁平。
            if (rank.get(rootP) > rank.get(rootQ)) {
                parent.put(rootQ, rootP);
            } else if (rank.get(rootP) < rank.get(rootQ)) {
                parent.put(rootP, rootQ);
            } else {
                parent.put(rootQ, rootP);
                rank.put(rootP, rank.get(rootP) + 1); // 如果秩相同，选择一个根，根 的 rank加1
//                rank.put(rootP, rank.get(rootP) + rank.get(rootQ));
            }
        }
    }

    // 添加新元素
    public void insert(int p) {
        if (!parent.containsKey(p)) {
            parent.put(p, p);
            rank.put(p, 0);
        }
    }
}
